package 剑指offer;

import java.util.HashMap;
import java.util.Map;

public class _55平衡二叉树 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        Map<TreeNode,Integer> map = new HashMap<>();
        int leftHeight = 0;
        int rightHeight = 0;
        if(map.containsKey(root.left)){
            leftHeight = map.get(root.left);
        }else{
            leftHeight = height(root.left);
            map.put(root.left,leftHeight);
        }
        if(map.containsKey(root.right)){
            rightHeight = map.get(root.right);
        }else{
            rightHeight = height(root.right);
            map.put(root.right,rightHeight);
        }
        int heightAbs = Math.abs(leftHeight - rightHeight);
        if(heightAbs > 1){
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }
    public int height(TreeNode root){
        if(root == null){
            return 0;
        }
        return 1 + Math.max(height(root.left),height(root.right));
    }
}
